package LeetcodeTest_fourteen;

//设计双端循环队列
public class myCircularDeques
{
    public static void main(String[] args)
    {
        MyCircularDeque myDeque=new MyCircularDeque(4);
        System.out.println(myDeque.insertFront(9));
        System.out.println(myDeque.deleteLast());
        System.out.println(myDeque.getRear());
        System.out.println(myDeque.getFront());
        System.out.println(myDeque.getFront());
        System.out.println(myDeque.deleteFront());
        System.out.println(myDeque.insertFront(6));
        System.out.println(myDeque.insertLast(5));
        System.out.println(myDeque.insertFront(9));
        System.out.println(myDeque.getFront());
        System.out.println(myDeque.insertFront(6));
    }
}
class MyCircularDeque
{
    public int capacity;     //队列容量
    public int numOfelement;   //队列元素个数
    CircularDeque head;//哨兵节点
    CircularDeque rear;//哨兵节点
    /** Initialize your data structure here. Set the size of the deque to be k. */
    public MyCircularDeque(int k)
    {
        head=new CircularDeque(0);
        rear=new CircularDeque(0);
        head.next=rear;
        rear.forward=head;
        numOfelement=0;
        capacity=k;
    }
    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    public boolean insertFront(int value)
    {
        if(numOfelement<capacity)
        {
            CircularDeque p1 = new CircularDeque(value);    //p1保存新插入的节点
            CircularDeque p2=head.next;                    //p2记录头节点的后继
            head.next=p1;
            p1.next=p2;
            p2.forward=p1;
            p1.forward=head;
            numOfelement++;
            return true;
        }
        else
            return false;
    }
    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value)
    {
        if(numOfelement<capacity)
        {
            CircularDeque p1 = new CircularDeque(value);      //p1保存新插入的节点
            CircularDeque p2=rear.forward;                    //p2记录尾节点的前趋
            p1.next=rear;
            p2.next=p1;
            rear.forward=p1;
            p1.forward=p2;
            numOfelement++;
            return true;
        }
        else
            return false;
    }
    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront()
    {
        if(numOfelement!=0)
        {
            head=head.next;
            head.forward=null;
            numOfelement--;
            return true;
        }
        else
            return false;
    }
    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast()
    {
        if(numOfelement!=0)
        {
            rear = rear.forward;
            rear.next = null;
            numOfelement--;
            return true;
        }
        else
            return false;
    }
    /** Get the front item from the deque. */
    public int getFront()
    {
        if(numOfelement!=0)
            return head.next.val;//头节点
        else
            return -1;
    }
    /** Get the last item from the deque. */
    public int getRear()
    {
        if(numOfelement!=0)
            return rear.forward.val;//尾节点
        else
            return -1;
    }
    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty()
    {
        if(numOfelement>0)
            return false;
        else
            return true;
    }
    /** Checks whether the circular deque is full or not. */
    public boolean isFull()
    {
        if(numOfelement==capacity)
            return true;
        else
            return false;
    }
}
class CircularDeque
{
    int val;
    CircularDeque forward;   //节点的前趋
    CircularDeque next;      //节点的后继
    CircularDeque(int x)
    {
        this.val=x;
    }
}